package leetcode.biweekly.week97;

import java.util.Map;
import java.util.TreeMap;

//Solution3Test
public class Solution3 {

	public int maximizeWin(int[] prizePositions, int k) {
		if (prizePositions[prizePositions.length - 1] - prizePositions[0] <= k) {
			return prizePositions.length;
		}
		TreeMap<Integer, Integer> tm = new TreeMap<>();
		for (int i = 0, l = 0; i < prizePositions.length; i++) {
			int R = prizePositions[i];
			while (i + 1 < prizePositions.length && prizePositions[i + 1] == R) {
				i++;
			}
			int L = R - k;
			while (prizePositions[l] < L) {
				l++;
			}
			tm.put(R, i - l + 1);
		}
		int ans = 0;
		TreeMap<Integer, Integer> last = new TreeMap<>();
		int max = -1;
		for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
			max = Math.max(max, entry.getValue());
			last.put(entry.getKey(), max);
		}
		for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
			int cur = entry.getValue();
			if (last.floorKey(entry.getKey() - k - 1) != null) {
				cur += last.get(last.floorKey(entry.getKey() - k - 1));
			}
			ans = Math.max(ans, cur);
		}
		return ans;
	}
}
